package sort;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {12,343,543,65,4,35,7,8,6,4,64,6};
        heapSort(arr);
    }

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2){
            return;
        }
//        for (int i = 0; i < arr.length; i++) {
//            // 将所有元素入堆，此时0位置的就是最大的-->变成大根堆
//            heapInsert(arr,i);
//        }
        // 变成大根堆
        for (int i = arr.length-1; i >= 0; i--) {
            heapIfy(arr,i,arr.length);
        }

        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while (heapSize > 0){
            heapIfy(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }
    }

    // 向下比较
    public static void heapIfy(int[] arr,int index,int heapSize){
        int left = index*2+1;
        while (left < heapSize){
            // 求左孩子和右孩子的较大值的坐标
            int largestIndex = (left+1 < heapSize && arr[left+1] > arr[left]) ? left+1 : left;
            largestIndex = arr[largestIndex] > arr[index] ? largestIndex : index;
            if (largestIndex == index){
                break;
            }
            swap(arr,largestIndex,index);
            index = largestIndex;
            left = index*2+1;
        }
    }
    // 向上比较
    public static void heapInsert(int[] arr,int index){
        while (arr[index] > arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            index = (index-1)/2;
        }
    }
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
